package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;
/**
 * 这里 在做 一个 最新版的   小解释 :
 * 	int arrows = 100000;
	int arr[] = {0,0,0,0,0,0,0,0,0,0,0,100000};
	对于 这个 特殊的 案例 来说 下面       solution 和 solutonTwo   的 写法 会有 一些 问题 
	对于 solution 和 solutionTwo 来说   有一个
	共同点   就是                         MaxScore  (射箭的最大得分)  是  全局   变量 
			if(arrows - arr[i] >= 1) {
				process(arr,arrows - arr[i]-1,i + 1,tempScore + i);
				
			}
			else {
				process(arr,arrows,i + 1,tempScore);
			}  
	对于  上面的 代码  如果 把  else  	process(arr,arrows,i + 1,tempScore);
	这句代码 注释掉的 话那么 上面 这个 测试 样例 就无法 通过   其实小小思考一下 也能够明白 为啥 
	因为 maxScore  是全局 变量 只有 在   basecase     的 时候 才会 被赋值 
		if(index == 12 || arrows == 0) {
			if(max  < tempScore) {
			max = tempScore;	
			}
			return;
	这两个 递归函数的 basecase 都不会 有机会 被执行 
	不会到达 index =12 或者 arrows 为  0 情况 不仅仅 上面 这个  测试样例 
	 只要 满足 此种 条件的 测试 样例 都不会 过 
	 所以   尝试着 构造           对数器
	 这种复杂 的 题 暴力 解法 写出来 就已经 很费劲了 
	该题 深刻 的 说明   递归  暴力 解法  不一定是 一种   效率 比较差的 方法 
	 
	 但是 processFinal  和 dpFinal    处理 这种 案例 是没有 问题的   
	
 * 
 * 
 * 
 */
import java.util.Arrays;

/**
 * 这道题 真的 是   经典中 得 经典 题  
 * dp 也可以  写 
 * 回溯 递归 也可以写  
 * 
 * 这还可以 看成是   组合求和 问题得   变种 问题 只不过 比那 更难一些 
 * 
 * 这个  用回溯 来写  是属于 比较叼 的  回溯 思想的 运用了
 * 
 * 
 * 这个 题的难点 是在于 计算 最大得分 而在于
 * 返回的 是一个数组  这怎么 做到 算出 最大 得分的 同时 
 * 把数组 中的 数值 对应上呢  
 * 	 * 可以 用 int temp 做中间变量  
	 * 同样  也可以 用一个数组 作为中间变量  这不是一样的 道理  嘛
	 * 
	 * 
 * @author I adore you
 *  这里  起初 最大 得 问题 在于 这个         结果 ans  数组  声明为 全局变量  还是 局部变量得 问题 上面 花费 了 一些 时间的  
 *  还是这个 问题 你在 一个 方法  体 内部  对         局部变量 （或者 函数的 参数 ） 进行赋值 
 *  该函数 执行 结束 后  是无法 传递 出去的 
 * 这再 递归 里面  体现的             尤为真实      起初 的时候  ans 数组的 值 全部 为 0           
 * 
 * debug的 时候                    引用数据 类型 的 变量 会有 一个 id 属性 这相当于 地址对应 转换的 一个 id 其实 也就 对应着 地址对吧   
 * 
 * 注意 暴力递归的   时候 是  两种 做法  ：
 *  一种           递归 中    嵌套   for循环 来进行 暴力递归
 *  第二种 ：  就是 递归 中不  使用for 循环 直接 进行 代码 coding 
 *  常见的 这种 就是  
 *  要  或者 不要
 *  选 或者 不选    
 * 
 * 其实 区别 是 啥 
 * 就是  第一种 是 构建        多叉树   对吧 
 * 第二种  是 构建      二叉树 
 * 效率 而言 的 话
第一种：  1499 （进入 bacase 的次数）
 第二种： 2460  （进入 basecase的次数 ）
虽然 这个  进入basecase 的 次数 并不代表着  效率 的 高低 但是 
一定层度 上 还是 能反映 的 对吧 
如果 两种  暴力 递归  都可以的  话
推荐 使用第二种

其实第一种 也有 其 又是对吧

 * 
 */
public class leetcode2212射箭比赛中的最大得分 {
	
	static int maxScore = 0;
	static int ans[] = new int [12];
	public static int [] solution(int numArrows,int []aliceArrows) {
//		int ans []= new int [12]; 
		/**
		 * 这 里的 maxScore 传入的 初始参数 是 0
		 * 得分   不可能  为负数  传个 0  就可以了 
		 */
		process(numArrows,aliceArrows,new int [12],1);
		
		return ans;
	}
	/**
	 * 可以 用 int temp 做中间变量  
	 * 同样  也可以 用一个数组 作为中间变量  这不是一样的 道理  嘛
	 */
	public static void process(int arrows,int arr[],int temp[],int index) {
/**
 * 这里 要有 一个 索引 过滤条件的  index 可能 会  越界 
 * 可以 在这里  控制 也可以  在for 循环中控制 这个月结的处理
 * 这个 索引 条件 好像 不用管 
 * 对于该题 来说  ？？？
 */
		count++;
		if(arrows == 0 || index == 12) {
				 if(maxScore  < temp[0]) {
					 ans = Arrays.copyOf(temp,12);
					 maxScore = temp[0];
//					 if(arrows > 0) {
//						 ans[]
//					 }
//					 ans[0] = arrows;
/**
 * 					   这里还是有所 顾及的 对吧  因为 这里 始终就传入 一个 temp   的引用地址
 * 					 再 这里考虑了 一下  把 这个   temp  重置为 0 
 * 					但是 这个操作  可以 在回溯 中进行的  这 不更加 合理  
 * 					 ans[0] = arrows;  这个 代码  不能 放在 内层 
 * 					if的外面的  会出错的  
 * 					其实 想一下 也能明白 是什么  情况
 * 					
 */
				 }
				return ;
			}
//		                                 这个 剪枝 是必要的 一部分 对吧  solution(arrows,arr)   
			for(int  i = index ; i < 12 ;i++) {
				if(arrows - arr[i]>= 1) {
					temp[0] += i;
					temp[i] = arr[i] + 1;
					process(arrows - temp[i],arr,temp,i+1);
					temp[0] -= i;
					temp[i] = 0;					
				}
				else {
					process(arrows,arr,temp,i+1);
				}
			}
	}
	/**
	 * 先来个 简单的 dp
	 * 
	 * 先写个 简单的 暴力 递归 就是 求出 最大 得分 对吧 
	 * 就求出 最大 得分 
	 * 虽然 这个 求出 最大 分 算出来了 但是 有点 意外
	 * 
	 * 
	 * 这跟           1014     <最佳观光组合>  求最值 是不一样的 你发现 没
	 * 		int score = 0;
		  for(int i = index +1; i < values.length  ;i++) {
			  int score1 = values[index] +values[i] + index - i; 
//			  score = Math.max(score1, solution(values,i));
			  score = Math.max(score,Math.max(score1, solution(values,i)));
		}
		 return score;
	 *
	 * 区别 在  哪???
	 * 在于          能  区分  出  最值 的      时机   不一样  
	 * 1014 这个 题 的 最值   是 collection[i] 和    collection[i+1]  都可能 是最值
	 * 意思 就是  集合 collection 中的 每一个 元素  都可能    最值        MAX 的 候补 
	 *所以      score = Math.max(score,Math.max(score1, solution(values,i)));
	 *这样写 很合理 
	 * 
	 * 而 2212    这道题  区分 最值 是在 什么 时候  是在   basecase  的时候 
	 * 也就是 递归出口 的 时候 才能 做判断  
	 * 所以 这个 最值 是  从  collection 的   index 位置   收集  (所谓的  收集 也就是 求和 sum )  满足 条件的   元素  到  basecase ( 递归出口 )
	 * 才能 与上一次 的 收集 结果 进行 判断 从而 挑选出 最大值    
	 * 注意 这个 过程 不一样 
	 * 所以 我就 很好奇 这个 dp  是怎么写 的 
	 */
	static int max = 0;
	public static int solutionTwo(int arrows,int arr[]) {
		process(arr,arrows,0,0);
//		process(arr,arrows,1,0);  这两个 是 一样的结果 这理解 很简单 对吧 
			return max ;
	}
	public static void  process(int arr[],int arrows,int index,int tempScore) {
		/**
		 * 什么 是 basecase 
		 * 递归的 出口 
		 * 就是 结束的 时候
		 * 这个 递归的 结束 条件 是
		 * arrows = 0 或者 走到 数组的  末尾
		 * 这都是 递归 应该结束的 时候
		 * 
		 * 这里 对递归 又有 新的 理解 
		 */
		if(index == 12 || arrows == 0) {
			if(max  < tempScore) {
			max = tempScore;	
			}
			return;
//			return 0;
		}
//		int maxScore = 0;
		for(int i = index; i < 12; i++) {
			if(arrows - arr[i] >= 1) {
				process(arr,arrows - arr[i]-1,i + 1,tempScore + i);
				
			}
			else {
				/**
				 * 这里 说明  arr[i]  选不了 
				 * 下面的 代码 就是 跳过 arr [i] 去执行
				 */
				process(arr,arrows,i + 1,tempScore);
			}
			
		}
	}
/**
 * 写一个 跟上面 void 版本 不一样 的  递归 回溯 返回 值 int 	
 * 
 * 
 * 这个 版本 的递归 回溯 还是 没有 写出来  
 */
 public static int process(int arr[],int arrows,int index) {
	 if(index == 12 || arrows ==0) {
		 
		 return 0;
	 }
	 int score1 = 0;
	 int score2 = 0;
	 for(int i = index; i<=11; i++) {
		 score1 += process(arr,arrows,i+1);
		 if(arrows - arr[i] >= 1) {
//			 score +=i;
//			score += Math.max(score + i, process(arr,arrows - arr[i] -1,i+1)); 
//			score2 += Math.max(score, process(arr,arrows - arr[i] -1,i+1)+i); 
			 score2 +=process(arr,arrows - arr[i]- 1,i + 1) + i;
		 }
//		 else {
//			 score = process(arr,arrows,i+1);
//		 }
	 }
//	 return score;
	 return Math.max(score1,score2);
 }
	
/**
 * 思考 之后的 版本  
 * 来 try   
 * 卧槽   直接成功 了   记住 这历史性的   一刻 
 * 
 * 
 * 来回 去 复习 这个 过程所学到的   很多 东西 这里 面 
 * 	一天 三复习 就行
 */
 public static int processOne(int arr[],int arrows,int index) {
	 if(index == 12 || arrows ==0) {
		 
		 return 0;
	 }
	 int score = 0;
//	                这里 写          arrows - arr[i] >= 1这是错的  这里 真的 很绕
	 for(int i = index; i< 12; i++) {
		 if(arrows -arr[i] >= 1) {
			 score = Math.max(score, processOne(arr,arrows - arr[i] -1,i + 1) + i);
		 }
		 else {
			 score = Math.max(score, processOne(arr,arrows,i + 1));
		 }
	 }
	 return score;
 }
 /**
  *下面 这个 方法 的结果 跟  结果 跟上 
  * 
  * 
  */
 static int a;
 public static int processFinal(int arr[],int arrows,int index) {
	 a++;
	 if(index == 12 || arrows ==0) {
		 
		 return 0;
	 }
	 int score = 0;
//	                这里 写          arrows - arr[i] >= 1这是错的  这里 真的 很绕
	 for(int i = index; i < 12; i++) {
		 if(arrows -arr[i] >= 1) {
			 score = Math.max(score, processFinal(arr,arrows - arr[i] -1,i + 1) + i);
		 }
//		 else {
//			 score = Math.max(score, processFinal(arr,arrows,i + 1));
//		 }
	 }
	 return score;
 }
 
 /**
  * 尝试  着 直接 把 原题           <射箭比赛中的 最大得分>   真正 的应该返回的 结果   给写出来
  * 返回 一个 结果 数组            int ans [] = new int [12];
  * 
  * 
  * 总感觉  可以 写出来 跟 solution  这个 递归 回溯 不一样的 方法 但是 
  * 现在 还没 成功  
  * 但 我总 感觉  能写 出来 
  * 等忙过 这 一 阵 子 再来 探究 一下 这个 问题 
  * 
  */
 static int res [] = new int[12];
 public static int processFianlSolution(int arr[],int arrows,int index) {
	 if(index == 12 || arrows ==0) {
		 
		 return 0;
	 }
	 int score = 0;
	 int  temp = 0;
//	        在 for   循环     里 面   写    arrows - arr[i] >= 1这是错的  这里 真的 很绕
	 for(int i = index; i< 12; i++) {
		 if(arrows -arr[i] >= 1) {
			 temp = processFianlSolution(arr,arrows - arr[i] -1,i + 1) + i;
			 if(score < temp) {
				 score = temp;
				 temp = arr[i] +1;
			 }
//			 score = Math.max(score, processFianlSolution(arr,arrows - arr[i] -1,i + 1) + i);
//			 res[i] = value;
		 }
//		 else {
//			 score = Math.max(score, processFianlSolution(arr,arrows,i + 1));
//		 }
	 }
	 res[index] = temp;
	 return score;
 }
 
 
 
 /**
  * 把上面 这个 正确的   回溯递归 改成 dp
  * 改成 dp  之后 有没有 优化 取决 于 原递归 中 
  * 有没有 重复的 子过程的 运算 
  * 其实 这个 挺明显  的 是有的  
  * 
  */
 
public static int dpOne(int arrows,int arr[]) {
	int dp [][] =new int [arr.length+1][arrows+1];
	/**
	 * 
	 * 回溯 递归  函数中 有两个 变量  index   注意看 回溯 中 index  是可以 取值 为 12的    
	 *             arrows
	 * 所以 这个 dp 表 就是   二维数组
	 * 
	 * 下面这种 填表的 顺序 非常的 规范 理解 起来  就 很正常对吧 
	 * 画个 二维表 就知道 该按照 什么  样的顺序 去 填了
	 * 第三个 嵌套的 for  循环 绝对 是可以 优化 的 
	 * 从目前的 情况 来看  
	 * 
	 */
	for(int index = 11; index >= 0; index--) {
		for(int arrow = 1; arrow <= arrows; arrow++ ) {
			int score = 0;
			for(int i = index ;i <= 11;i++) {
				if(arrow - arr[i] >= 1) {
					score = Math.max(score,dp[i+1][arrow - arr[i] -1] + i);
				}
				/**
				 * 下面这个  else 代码  是可以 注释掉的  没有必要写
				 * 
				 * 
				 */
//				else {
//					score = Math.max(score, dp[i+1][arrow]);
//				}
			}
			dp[index][arrow] = score;
		}
	}
//	for(int i[] :dp) {
//		for(int j :i) {
//			System.out.print(j + " ");
//		}
//		System.out.println();
//	}
//	return dp[0][arrows];  返回 这两个 哪一个 都行 
	return dp[1][arrows];
	
}
/**
 * dp 优化 的 最终版本 
 * 终于 出来 了 
 * 一定要 记住 这两个 
 * 一个 是            < 组合 求和 问题>  的 dp 最终 优化图 
 * 一个 是 这个 <射箭比赛 中的最大 得分问题> 这个 的 dp 最终优化 图
 * 不错 也成功 了   最终 优化 
 * 通过 这个     <射箭比赛的最大得分 >   和 <组合求和 >  这两 最终版本的  动态规划 
 * 优化 枚举 行为的 过程 (          就是 把 最内层的         for循环    直接    优化 掉  )
 * 发现 优化 的 入手点 都是 (index +1 ,rest) 这个 坐标 
 * 所以 这也为 以后   写题 注意一下 思考的 方向 
 * 
 * 
 * 还有 一个 问题 对于 该题  来说 就是 怎么 倒推 出 这个 目标 数组 
 * 因为 dp 动态 规划 是不关注 过程 的 注重结果 
 * 其实 这样的  话 不如 直接  递归 回溯 中 进行   填表(更新 这个 目标数组)  
 * 
 * 暴力 递归 是很重要的 一种 法
 */
public static int dpFinal(int arr[] ,int target) {
	/**
	 * 为啥 是 13
	 *  因为 可以 取到 12 所以 要 声明 为 13;
	 *  为啥 上面的  dpOne 不用 声明 13 因为 
	 *  这道题  没有 初始化的步骤 
	 *  都是 0 呗
	 */
	int dp [][] = new int[13][target + 1];
	/**
	 * rest ==  0 return 0;
	 * index == 12 return 0;
	 * basecase  就是dp 表初始化 的 依赖 保证
	 */
	for(int index = 11; index >= 0 ;index-- ) {
		for(int rest = 1; rest <= target ;rest++) {
			dp[index][rest] = dp[index+1][rest];
			if(rest - arr[index] >= 1) {
			dp[index][rest] = Math.max(dp[index][rest],dp[index + 1][rest - arr[index] -1] + index);
			}
		}
	}
//	for(int i []: dp) {
//		for(int j : i) {
//			System.out.print(j + " ");
//		}
//		System.out.println();
//	}
	return dp[1][target];
}




/**
 * 下面测试一下   非正常顺序  填 表   来尝试  一下 
 *  index  和 arrows 都 从小到大  进行填表 这种 按照 直观理解 是错误的 
 *  
 *  结果 验证 也是 错的   因为 填表的 顺序 就是错的 
 *  下面  那些类 中  的   dp 方法    应该 是    按照  sum  index 这种形式 的回溯 递归 来 改的  dp
 *  而 我是 按照   rest  index  这种形式的 递归   来改写的 dp 
 *  两者的 区别 在于 ：
 *  index  没有 区别 都是 从 0  ~ 12
 *  而   sum  是 从   0 ~  arrows  变化 
 *  rest   是从  arrows ~ 0   变化 
 */
public static int dpTwo(int arrows,int arr[]) {
	int dp [][] =new int [arr.length+1][arrows+1];
	/**
	 * 
	 * 回溯 递归  函数中 有两个 变量  index   注意看 回溯 中 index  是可以 取值 为 12的    
	 *             arrows
	 * 所以 这个 dp 表 就是   二维数组
	 * 
	 * 下面这种 填表的 顺序 非常的 规范 理解 起来  就 很正常对吧 
	 * 画个 二维表 就知道 该按照 什么  样的顺序 去 填了
	 */
	for(int index = 1; index <= 11; index++) {
		for(int arrow = 1; arrow <= arrows; arrow++ ) {
			int score = 0;
			for(int i = index ;i <= 11;i++) {
				if(arrow - arr[i] >= 1) {
					score = Math.max(score,dp[i+1][arrow - arr[i] -1] + i);
				}
				else {
					score = Math.max(score, dp[i+1][arrow]);
				}
			}
			dp[index][arrow] = score;
		}
	}
//	return dp[0][arrows];  返回 这两个 哪一个 都行 
	return dp[1][arrows];
	
} 
 


	
/**
 * 这个 dp 是根据  上面 这个  递归 回溯 求 最大分数 的  暴力递归   改写的  
 * 
 */
    public static int dp(int arr[],int arrows) {
//    	 arr.length = 12 ; 这是 定值 啊 
    	int dp [][] = new int [12][arrows+1];
    		for(int arrow = 1;arrow <= arrows;arrow++ ) {
    			 for(int index = 1; index <= 11; index++) {
    				 
    			 }
    		}
    	
    	return 0;
    		
      }
	
	
/**
 * 改 dp 的 前提 是 思考一下  这有没有   重复的  子  过程
 * 对于 该题 而言 显然 是  有的  对吧	
 * 这个 dp  数组 怎么 设置 
 * index  变   arrows 箭的数量 也在变 对吧 
 * 还有 这个 temp 数组 也在变 ？？？  先不管 这个 temp 数组
 * 这个 dp 怎么 写 卧槽 
 */
	
	public static int [] dp(int num,int arrows[]) {
		int ans[] = new int [12];
		int  dp[][] = new int[13][num+1];
//		初始化 
		
		
		
		return ans;
	}
	
	static int count ;
	public static void main(String []args) {
		int arrows = 100000;
		int arr[] = {0,0,0,0,0,0,0,0,0,0,0,100000};
//		int arrows = 9;
//		int arrows = 3;
//		int arr[] = {1,1,0,1,0,0,2,1,0,1,2,0};
//		int arr[] = {0,0,1,0,0,0,0,0,0,0,0,2};
//		int arr[] = {1,4,3,1};
		String ans = Arrays.toString(solution(arrows,arr)); 
		System.out.println(ans);
		System.out.println(count);
//		Solution s = new Solution();
//		s.dfs(arr,0,arrows,0,new int [12]);
//		System.out.println(s.count);
		solutionTwo(arrows,arr);
		System.out.println(max);
////		System.out.println(process(arr,arrows,0));
//		System.out.println(processOne(arr,arrows,1));
//		System.out.println(dpOne(arrows,arr));
////		System.out.println(dpTwo(arrows,arr));
//		SolutionOne one = new SolutionOne();
//		one.maximumBobPoints(arrows, arr);
		System.out.println(processFinal(arr,arrows,1));
		System.out.println(dpFinal(arr,arrows)); 
		System.out.println(a);
		System.out.println(Arrays.toString(res));
	}
}
/** 
 * 这是 上面 回溯代码的   启发 原始代码
 * 这是 一种二叉树 的 暴力 递归 
 * 你写的 是一种             多叉树的   暴力递归 
 * 
 * 递归 回溯 都可以 转换成  一个 图.树 (  二叉树 或者 多叉树      )
 */
class Solution {
	int count;
    int max = 0;
    int[] ans = new int[12];
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        dfs(aliceArrows,0,numArrows,0,new int[12]);
        return ans;
    }

    void dfs(int[] nums, int idx, int res, int point,int[] cur){
    	count++;
        if(idx == 11){
            if(point>max){
                max = point;
                ans = Arrays.copyOf(cur,cur.length);
                if(res > 0){
                    ans[0] = res;
                }
            }
            return;
        }
        if(res > nums[idx+1]){
            cur[idx+1] = nums[idx+1]+1;
            dfs(nums,idx+1,res-nums[idx+1]-1,point +idx+1,cur);
        }
        cur[idx+1] = 0;
        dfs(nums,idx+1,res,point,cur);
    }
}
/**
 * 
 * 他这个 dp 的 转换 完全 是 根据   二叉树 暴力 递归 改写 的  很明显 对吧 
 *

* 下面测试一下   非正常顺序  填 表   来尝试  一下 
*  index  和 arrows 都 从小到大  进行填表 这种 按照 直观理解 是错误的 
*  
*  结果 验证 也是 错的   因为 填表的 顺序 就是错的 
*  下面  那些类 中  的   dp 方法    应该 是    按照  sum  index 这种形式 的回溯 递归 来 改的  dp
*  而 我是 按照   rest  index  这种形式的 递归   来改写的 dp 
*  两者的 区别 在于 ：
*  index  没有 区别 都是 从 0  ~ 12
*  而   sum  是 从   0 ~  arrows  变化 
*  rest   是从  arrows ~ 0   变化
*  就算 这个 时候   还是      解释不通  下面的    这个 叼毛 的 填表 顺序 啊 卧槽 
*  而且 下面 三个  dp   的 填表顺序  都是  一样的  
*  这就 让我 很疑惑 了      
*/
class SolutionOne{
    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        //0-1背包问题
        int n = aliceArrows.length;
        int[][] dp = new int[numArrows + 1][n + 1];
        for(int i = 1; i <= numArrows; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i][j-1];
                if(i - aliceArrows[j - 1] - 1 >= 0){
                    dp[i][j] = Math.max(dp[i][j], dp[i - aliceArrows[j - 1] - 1][j - 1] + j - 1);
                }
            }
        }

        //倒着求路径，可以把矩阵打出来想想怎么求
         for(int i [] : dp){
             for(int j : i){
                 System.out.print(j + " ");
             }
             System.out.println();
         }

        //统一把多余的箭放到不得分的0位置上；
        int[] ans = new int[12];
        int sum = 0;
        for(int i = numArrows, j = n; i >= 0 && j >= 1 ; ){
            if(j == 1) ans[j - 1] = numArrows - sum; 
            if(dp[i][j] != dp[i][j-1])  ans[j-1] = aliceArrows[j-1]+1;
            sum += ans[j - 1];
            i = i-ans[j - 1];
            j = j-1;
        }
        return ans;


    }
}
/**
 * 
 * 01 背包 问题 
 * 我感觉  我自己 写 的 那个回溯 
 *现在   我 改   不成 动态 规划 
 *我感觉 在 学完  背包 问题 后 可能  能写出来 
 *
 */
class SolutionThree{
	   public int[] maxValue(int N, int C, int[] weight, int[] value) {
	        int[][] dp = new int[N][C + 1];
	        int[][] path = new int[N][C + 1];

	        for (int i = 0; i <= C; i++) {
	            dp[0][i] = i >= weight[0] ? value[0] : 0;
	        }
	        for (int i = 1; i < N; i++) {
	            for (int j = 0; j < C + 1; j++) {
	                // 不选该物品
	                int n = dp[i-1][j];
	                // 选择该物品，前提「剩余容量」大于等于「物品体积」
	                int y = j >= weight[i] ? dp[i-1][j - weight[i]] + value[i] : 0;
	                //是否选择当前路径
	                path[i][j] = n > y ? 0 : 1;
	                dp[i][j] = Math.max(n, y);
	            }
	        }

	        //进行路径还原
	        int t = C;
	        int [] ans = new int[12];
	        for (int i = 11; i >= 0; i--) {
	            if (path[i][t] == 1 && t >= weight[i]) {
	                ans[i] = weight[i];
	                t = t - weight[i];
	            } else {
	                ans[i] = 0;
	            }
	        }
	        if (t > 0) ans[0] += t;
	        return ans;
	    }
/**
 * 下面的 代码 是有问题 的 要注意一下
 * 只是 为了 修改 不报错 
 */
	     public int[] maximumBobPoints(int p, int[] v) {
	    	 int weight[] = new int [12];
	        for (int i = 0 ; i < v.length; i++) {
	            weight[i]++;
	        }
	        int [] value = new int[]{0,1,2,3,4,5,6,7,8,9,10,11};
	        return maxValue(v.length, p, weight, value);
	    }
	}
/**
 * 下面 来  写 相对于 该题 目 《射箭比赛中的 最大得分 》 容易一点的 版本 
 *  对   这道题 进行 解释一下 就是 
 *  如果 Bob 在 某区域   中 的射箭 中的 数目 >=  Alice 的 箭的 数目 就能得 i 分 
 *  其实 可以 理解 成另外 一个 问题就是 
 *  共有  sum  钱数 
 *花费 arr[i] 可以 到  i 价值得 物品 
 *问 sum 钱数 能获得 得最大 物品的 价值是多少    
 *完全一 样  的 问题  这是 
 */
class SolutionFour {
	/**
	 * 这跟 组合 求和 问题 有所 不同  啊 
	 * 这里 因为 这个 集合 arr  是无序的 
	 * 不能 写 sum - nums[i] >=0;
	 * 这种去重的 行为出现的 
	 * 
	 * 
	 */
	public int process(int arr[],int arrows,int index) {
		if(arrows == 0 || index == 12) {
			return 0;
		}
		int score = 0;
		for(int i = index ;i <= 11 && arrows - arr[i]>= 0;i++) {
			score = Math.max(score, process(arr,arrows - arr[i],i+1) + i);
		}
		return score;
	}
	
	
}


